package medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @author gh
 * @create 2021-05-28 8:30
 */
public class lee477_totalHammingDistance {

    //暴力。结果：超时
    public int totalHammingDistance1(int[] nums) {
        int sum = 0;

        Map<Integer, Integer> map = new HashMap<>();
        int i = 0;
        for (int e : nums) {
            map.put(i, e);
            i++;
        }

        Map<Integer, Integer> map2 = new HashMap<>();
        map2.putAll(map);
        for (Integer key : map.keySet()) {
            Integer value = map.get(key);

            map2.remove(key,value);
            for (Integer key2 : map2.keySet()) {

                sum += HammingDistance(value, map2.get(key2));

            }
        }
        return sum;
    }

    public int HammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }

/*方法一：逐位统计
在计算汉明距离时，我们考虑的是同一比特位上的值是否不同，而不同比特位之间是互不影响的。对于数组 nums 中的某个元素val，若其二进制的第 i 位为 1，我们只需统计nums 中有多少元素的第 i 位为 0，即计算出了val 与其他元素在第 i 位上的汉明距离之和。

具体地，若长度为 n 的数组ums 的所有元素二进制的第 i 位共有 c 个 1，n−c 个 0，则些元素在二进制的第 i 位上的汉明距离之和为c⋅(n−c)

我们可以从二进制的最低位到最高位，逐位统计汉明距离。将每一位上得到的汉明距离累加即为答案。

具体实现时，对于整数val 二进制的第 i 位，我们可以用代码 (val >> i) & 1 来取出其第 i 位的值。此外，由于 10^9<2^30 ，我们可以直接从二进制的第 0 位枚举到第 29 位。

*/
    //复杂度分析
    //时间复杂度：O(n⋅L)。其中 n 是数组nums 的长度，L=30。
    //空间复杂度：O(1)。

    public int totalHammingDistance2(int[] nums) {
        int ans = 0, n = nums.length;
        for (int i = 0; i < 30; ++i) {
            int c = 0;
            for (int val : nums) {
                c += (val >> i) & 1;
            }
            ans += c * (n - c);
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] nums = {4,14,2};

        System.out.println(new lee477_totalHammingDistance().totalHammingDistance1(nums));
    }
}
